/**
 * @author Xiang.Yu
 * @version 0.0.1
 * @date 2017/3/16
 * @description backpack
 */
export const Cell = function (copy) {
    if (copy) {
        return {
            value: copy.value,
            list: copy.list.concat()
        }
    } else {
        return {
            value: 0,
            list: []
        }
    }
};

/**
 * 结果矩阵
 * @returns {Array} {物品序号{预估重量}}
 * @constructor
 */
export const Matrix = function (stuffSize=1,maxWeight=1) {
    let matrix = [];
    for(let i=0;i<stuffSize;i++){
        matrix[i] = [];
        for(let j=0;j<maxWeight+1;j++){
            matrix[i][j] = new Cell();
        }
    }
    return matrix;
};

export const Stuff = function (weight, value, name) {
    return {
        name: name,
        weight: weight,
        value: value
    }
};

/**
 * 计算背包可以放入的东西,使得价值最高
 * @param stuffs 待放入东西列表
 * @param maxWeight 最大重量
 * @returns {{matrix: Matrix 结果矩阵, list: (Array) 放入东西列表, totalWeight: number 放入的总重量, amount: number 放入的总价值}}
 * @constructor
 */
export const Backpack = function (stuffs=[], maxWeight=0) {
    debugger;
    let matrix = new Matrix(stuffs.length,maxWeight);
    //计算放入第一个东西
    for (let w = 0; w <= maxWeight; w++) {
        if (w >= stuffs[0].weight) {
            matrix[0][w] = new Cell();
            matrix[0][w].value = stuffs[0].value;
            matrix[0][w].list.push(stuffs[0]);
        }
    }
    //计算放入剩余东西
    for (let i = 1; i < stuffs.length; i++) {
        let stuff = stuffs[i];
        //w表示当前尝试重量
        for (let w = 0; w <= maxWeight; w++) {
            //不放入当前东西
            matrix[i][w] = new Cell(matrix[i - 1][w]);
            //判断能否放入当前东西
            if (w >= stuff.weight) {
                //能放入,计算放入当前东西后，还能放入最大的价值
                let valueAfter = stuff.value + matrix[i - 1][w - stuff.weight].value;
                //如果放入后比能放入价值更高，则放入，否则不放入
                if (valueAfter > matrix[i][w].value) {
                    matrix[i][w] = new Cell(matrix[i-1][w-stuff.weight]);
                    matrix[i][w].value = valueAfter;
                    matrix[i][w].list.push(stuff);
                }
            }
        }
    }
    let list=matrix[stuffs.length-1][maxWeight].list;
    let totalWeight = 0;
    let amount = 0;
    for(let stuff of list){
        totalWeight+=stuff.weight;
        amount+=stuff.value;
    }
    return {matrix,list,totalWeight,amount};
};